旅行商问题中巡回路径的数据结构

旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序,并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序,但是最坏情况下完成逆序操作需要Ω（n）时间,不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O（logn）,适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O（n^0.5）,适用于大规模的旅行商问题。     

基于粗糙变精度的食品安全决策树研究

食品安全决策是食品安全问题研究的一项重要内容。为了对食品安全状况进行分析,基于粗糙集变精度模型,提出了一种包含规则置信度的构造决策树新方法。这种新方法针对传统加权决策树生成算法进行了改进,新算法以加权平均变精度粗糙度作为属性选择标准构造决策树,用变精度近似精度来代替近似精度,可以在数据库中消除噪声冗余数据,并且能够忽略部分矛盾数据,保证决策树构建过程中能够兼容部分存在冲突的决策规则。该算法可以在生成决策树的过程中,简化其生成过程,提高其应用范围,并且有助于诠释其生成规则。验证结果表明该算法是有效可行的。     

QH-2型扁环填料的流体力学和传质性能研究

在内径60 0填料塔中 ,用空气 富氧水系统对3 8和5 0QH 2型扁环填料的流体力学和传质性能进行了研究 ,得出计算其压降、液泛气速和传质单元高度的关联式。并与3 8鲍尔环、5 0鲍尔环和3 8环矩鞍填料进行了比较 ,结果表明 ,QH 2型扁环具有优良的流体力学和传质特性。     

Near-duplicate document image matching: A graphical perspective

A near-duplicate document image matching approach characterized by a graphical perspective is proposed in this paper. Document images are represented by graphs whose nodes correspond to the objects in the images. Consequently, the image matching problem is then converted to graph matching. To deal with the instability of object segmentation, a multi-granularity object tree is constructed for a document image. Each level in the tree corresponds to one possible object segmentation, while different levels are characterized by various object granularities. Some graphs can be generated from the tree and the objects associated with each graph may be of different granularities. Two graphs with the maximum similarity are found from the multi-granularity object trees of the two near-duplicate document images which are to be matched. The encouraging experimental results have demonstrated the effectiveness of the proposed approach.     

Drawing non‐layered tidy trees in linear time

The well‐known Reingold–Tilford algorithm produces tidy‐layered drawings of trees: drawings where all nodes at the same depth are vertically aligned. However, when nodes have varying heights, layered drawing may use more vertical space than necessary. A non‐layered drawing of a tree places children at a fixed distance from the parent, thereby giving a more vertically compact drawing. Moreover, non‐layered drawings can also be used to draw trees where the vertical position of each node is given, by adding dummy nodes. In this paper, we present the first linear‐time algorithm for producing non‐layered drawings. Our algorithm is a modification of the Reingold–Tilford algorithm, but the original complexity proof of the Reingold–Tilford algorithm uses an invariant that does not hold for the non‐layered case. We give an alternative proof of the algorithm and its extension to non‐layered drawings. To improve drawings of trees of unbounded degree, extensions to the Reingold–Tilford algorithm have been proposed. These extensions also work in the non‐layered case, but we show that they then cause a O(n²) run‐time. We then propose a modification to these extensions that restores the O(n) run‐time. Copyright © 2013 John Wiley & Sons, Ltd.     

Variational Tree Synthesis

Modelling trees according to desired shapes is important for many applications. Despite numerous methods having been proposed in tree modelling, it is still a non‐trivial task and challenging. In this paper, we present a new variational computing approach for generating realistic trees in specific shapes. Instead of directly modelling trees from symbolic rules, we formulate the tree modelling as an optimization process, in which a variational cost function is iteratively minimized. This cost function measures the difference between the guidance shape and the target tree crown. In addition, to faithfully capture the branch structure of trees, several botanical factors, including the minimum total branches volume and spatial branches patterns, are considered in the optimization to guide the tree modelling process. We demonstrate that our approach is applicable to generate trees with different shapes, from interactive design and complex polygonal meshes.     

Crystalline complex between poly(γ-methyl l-glutamate) and dimethyl phthalate

The crystalline complex between poly(γ-methyl l-glutamate) (PMLG) and dimethyl phthalate (DMP) has been formed in films cast from a solution in dichloroethane. It has the stoichiometry of 1 mol of DMP to three or four residues of PMLG and shows two definite characteristics in X-ray diffraction patterns; one is the large hexagonal unit cell with the edge of around 28 Å and another the ‘extra’ 5.07 Å meridional reflection which can not be interpreted by a PMLG α-helical conformation. The structural examination for the films with various DMP contents is carried out by X-ray, viscoelastic, and d.s.c. measurements and the following structure is proposed for the crystalline complex. Four PMLG are associated to form a group which is hexagonally packed and DMP molecules, located in the gaps between groups, form a specific favourable helical structure along PMLG chains in which the van der Waals stacking of benzene rings of DMP is significant.     

最短路径算法在校园导游系统中的应用

用无向网表示学校的平面图,设计了该平面图的存储结构,并应用最短路径算法实现了查询图中各景点的相关信息,以及查询图中任意两个景点间的最短路径的功能;应用克鲁斯卡尔算法构造该平面图的最小生成树,求出可以连通所有景点的最短路径。该系统为新生熟悉校园环境提供了方便。     

基于糊模ID3算法的高校学生流失数据挖掘研究

目前高校不断扩招,生源却逐渐减少,于是预防和减少学生流失正成为各高校必须面对的问题。通过对高校学生流失情况进行数据挖掘,可发现一些有价值的信息,为解决高校学生流失问题提供帮助。基于糊模理论提出了糊模ID3算法,并将该算法运用于分析高校学生流失原因之中。通过实验证明,该算法生成的决策树更加合理,分类速度更快,为解决高校学生流失问题提供了理论依据。